/*
 * @lc app=leetcode.cn id=105 lang=cpp
 *
 * [105] 从前序与中序遍历序列构造二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 **/

/*前序遍历
void PreTraverseBTree(struct BTNode *pT)
{
  if (NULL != pT)
  {
    pT->data;

    if (NULL != pT->pLchild)
    {
      PreTraverseBTree(pT->pLchild);
    }

    if (NULL != pT->pRchild)
    {
      PreTraverseBTree(pT->pRchild);
    }
  }
}*/

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

struct TreeNode
{
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

/*class Solution
{
public:
  TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder)
  {
    return buildOneLevel(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
  }

  // 递归函数功能：构建树的某一层结构
  // 这里用下标法，需要6个形餐，也可以用迭代器只要4个形餐
  TreeNode *buildOneLevel(vector<int> &preorder, int pre_begin, int pre_end, vector<int> &inorder,
int in_begin, int in_end)
  {
    // 递归子函数的出口
    if (pre_begin > pre_end || in_begin > in_end)
      return NULL;

    // 先找根节点(用前序遍历序列)
    TreeNode *root = new TreeNode(preorder[pre_begin]);
    // 左子树长度
    int left_length = 0;
    for (int i = in_begin; i < in_end; i++)
    {
      if (inorder[i] == root->val)
      {
        left_length = i;
        // 先找到中序遍历序列中根节点的位置
        break;
      }
    }
    // 左子树长度
    left_length -= in_begin;

    // 左子树(在前序中范围是：pre_begin + 1～pre_begin +
left_length)(在中序的范围是：in_begin~in_begin+left_length - 1) ) root->left =
buildOneLevel(preorder, pre_begin + 1, pre_begin + left_length, inorder, in_begin, in_begin +
left_length - 1);

    //
右子数(在前序中范围是：pre_begin+left_length+1~pre_end)(在中序的范围是：in_begin+left_length+1,in_end)
    root->right = buildOneLevel(preorder, pre_begin + left_length + 1, pre_end, inorder, in_begin +
left_length + 1, in_end);

    // 递归母函数的出口
    return root;
  }
};*/

typedef struct TreeNode* pTreeNode;
// typedef vector<int>::iterator iter;  // 为便于书写，也可使用类型别名(同typedef)

class Solution
{
 public:
  TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
  {
    return buildOneLevel(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());
  }

  // 递归函数功能：构建树的某一层结构
  // template<typename iterator>
  // 也可直接用vector<int>::iterator类型，模板可以进行类型延伸(泛型编程)，避免不同类型写多个函数（自己的思考）,但函数内部的很多变量名需用auto
  using iter = vector<int>::iterator;  //为便于书写，也可使用类型别名 （同typedef）

  TreeNode* buildOneLevel(iter pre_begin, iter pre_end, iter in_begin, iter in_end)
  {
    // 递归出口一（除结尾外还需要一个内部return,即两个return吧）
    if (pre_begin == pre_end || in_begin == in_end) return nullptr;

    // 先找根结点(用前序遍历序列)
    TreeNode* root = new TreeNode(*pre_begin);  // 前序遍历序列首元素即为根结点

    // 在找左子树和右子树（用中序遍历序列） （具体只用求左子树序列长度就可以了）
    vector<int>::iterator in_root_pos = find(
        in_begin, in_end,
        root->val);  // 先找到中序遍历序列中根节点的位置 （由于序列中不含重复元素，故可以用此方法）

    int left_length = in_root_pos - in_begin;  // 左子树序列长度

    // 左子树(对于顺序容器的迭代器可以直接加某个常数，其他容器迭代器需用distance、next等函数)
    root->left = buildOneLevel(pre_begin + 1, pre_begin + left_length + 1, in_begin, in_root_pos);

    // 右子数
    root->right = buildOneLevel(pre_begin + left_length + 1, pre_end, in_root_pos + 1, in_end);

    // ！！注意end指向容器末尾（最后一个元素的下一个位置）
    return root;  // 递归出口二
  }

  // 自己的思路：
  
};

int main()
{
  pTreeNode pA = new TreeNode(3);
  pTreeNode pB = new TreeNode(9);
  pTreeNode pC = new TreeNode(20);
  pTreeNode pD = new TreeNode(15);
  pTreeNode pE = new TreeNode(7);

  pA->left = pB;
  pA->right = pC;

  pC->left = pD;
  pC->right = pE;

  vector<int> preorder;
  int myintA[] = {3, 9, 20, 15, 7};
  preorder.assign(myintA, myintA + 5);

  vector<int> inorder;
  int myintB[] = {9, 3, 15, 20, 7};
  inorder.assign(myintB, myintB + 5);

  Solution solute;
  TreeNode* root = solute.buildTree(preorder, inorder);
}

// @lc code=end
